package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 22:25 2020/8/19
 * @Description 01背包问题
 * 假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6
 * 现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。
 */

public class Packet0or1 {

    /**
     * 背包问题对于前N个物品只有两个选择，拿或者是不拿
     * 1.背包容量充足  拿还是不拿
     * 2.背包容量不足不能拿 dp[i][j]=dp[i-1][j]
     */
    public static int packet0or1(int[] weight, int[] value, int maxWeight) {

        //1.构造dp数组    weight.length是因为传入是已经多加了一个0了  0 - maxWeight   i为物品 j为背包大小
        int[][] dp = new int[weight.length][maxWeight + 1];

        //2.填写
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= maxWeight; j++) {
                if (j < weight[i]) dp[i][j] = dp[i - 1][j];
                else {
                    dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
                }
            }
        }
        //3.返回
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.printf("%d ", anInt);
            }
            System.out.println();
        }
        return dp[weight.length - 1][maxWeight];
    }

    public static void main(String[] args) {
        int n = 5, w = 10;                    //物品个数，背包容量
        // 红色代码注释开始
        int[] value = {0, 6, 3, 5, 4, 6};     //各个物品的价值
        int[] weight = {0, 3, 2, 6, 5, 4};    //各个物品的重量
        // 红色代码注释结束
        System.out.println(packet0or1(weight, value, w));
    }

}
